package exercises.leetcode;

import java.util.ArrayDeque;

/**
 * <a href="https://leetcode-cn.com/problems/longest-word-in-dictionary/">
 * 720. 词典中最长的单词</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。
 * <p>
 * 若无答案，则返回空字符串。
 *
 * @author or2
 * @date 2021年11月08日 时间: 9:18
 */
public class No720 {
    public String longestWord(String[] words) {
        var trie = new Trie();
        int idx = 0;
        for (String word : words) trie.insert(word, ++idx);
        trie.words = words;
        return trie.dfs();
    }

    private static class Node {
        char ch;
        Node[] children;
        int end;

        public Node(char ch) {
            children = new Node[26];
            this.ch = ch;
        }
    }

    private static class Trie {
        Node root;
        String[] words;

        public Trie() {
            root = new Node('0');
        }

        public void insert(String word, int index) {
            var cur = root;
            for (char ch : word.toCharArray()) {
                int bias = ch - 'a';
                if (cur.children[bias] == null) {
                    cur.children[bias] = new Node(ch);
                }
                cur = cur.children[bias];
            }
            cur.end = index;
        }

        public String dfs() {
            String ans = "";
            var stack = new ArrayDeque<Node>();
            stack.push(root);

            while (!stack.isEmpty()) {
                var node = stack.pop();
                if (node.end > 0 || node == root) {
                    if (node != root) {
                        var word = words[node.end - 1];
                        if (word.length() > ans.length() || (word.length() == ans.length() && word.compareTo(ans) < 0))
                            ans = word;
                    }
                    for (var nei : node.children)
                        if (nei != null)
                            stack.push(nei);
                }
            }

            return ans;
        }
    }
}
